package com.demo.datastructure.hashTable;

import com.demo.datastructure.hashTable.interFace.Table;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * @description:
 * @author: ljr
 * @time: 2021/5/17 8:06
 */
public class HashTableDemo2<K,V> implements Table<K,V>{


    private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    private static final int DEFAULT_MAX_CAPACITY = 1 << 30;

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 初始化散列表数组
     */
    private Node<K,V>[] table;

    /**
     * 实际元素数量
     */
    private int size;

    /**
     * 散列表索引数量
     */
    private int use = 0;


    public HashTableDemo2() {
        table = (Node<K, V>[]) new Node[DEFAULT_INITIAL_CAPACITY];
    }


    private int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    public void put(K key, V value) {
        int index = hash(key);

        if (table[index] == null) {
            table[index] = new Node<>(null, null, null);
        }

        Node<K, V> tmp = table[index];
        if(tmp.next == null){
            tmp.next = new Node<>(key,value,null);
            size++;
            use++;
            if (use >= table.length * DEFAULT_LOAD_FACTOR) {
                resize();
            }
        }else{
            do{
                tmp = tmp.next;
                if(tmp.key == key){
                    tmp.value = value;
                    return;
                }
            }while (tmp.next != null);

            tmp.next = new Node<>(key,value,null);
            size++;
        }


    }

    private void resize() {
        Node<K,V>[] oldTable = table;
        table = new Node[oldTable.length];
        use = 0;
        for (int i = 0; i < oldTable.length; i++) {
            if (oldTable[i] == null || oldTable[i].next == null) {
                continue;
            }

            Node oldNode = oldTable[i].next;
            while(oldNode != null){
                int index = hash(oldNode.key);
                if(table[index] == null){
                    table[index] = new Node<>(null,null,null);
                }
                table[index].next = new Node(oldNode.key,oldNode.value,table[index].next);
            }
        }
    }

    public void remove(K key) {
        int index = hash(key);
        if(table[index] == null || table[index].next == null){
            return;
        }

        Node header = table[index];
        Node pre = null;
        do{
           pre = header;
           header = header.next;
           if(header.key == key){
               pre.next = header.next;
               size--;
               if(table[index].next == null){ use--; }
               return;
           }
        }while (header.next != null);
    }


    public V get(K key) {
        int index = hash(key);
        if(table[index] == null || table[index].next == null){
            return null;
        }

        Node node =  table[index];
        do{
            node = node.next;
            if(node.key == key){
                return (V) node.value;
            }
        }while (node.next != null);

        return null;
    }


    private static class Node<K,V> implements Entry<K,V>{
        final K key;
        V value;
        Node<K,V> next;

        public Node(K key, V value, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }


        public final K getKey(){
            return key;
        }


        public final V getValue(){
            return value;
        }


        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public boolean equals(Object o){
            if(o == this){
                return  true;
            }

            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                return Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue());
            }
            return false;
        }

    }

}
